// 链表节点类
class ListNode {
    int val;        // 节点存储的数据
    ListNode next;  // 指向下一个节点的引用

    // 构造函数
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// 链表类
class LinkedList {
    ListNode head;  // 链表头节点

    // 1. 在链表末尾添加节点
    public void append(int val) {
        ListNode newNode = new ListNode(val);

        if (head == null) {
            head = newNode;
            return;
        }

        ListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 2. 在链表头部添加节点
    public void prepend(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
    }

    // 3. 删除指定值的节点
    public void delete(int val) {
        if (head == null) return;

        if (head.val == val) {
            head = head.next;
            return;
        }

        ListNode current = head;
        while (current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 4. 查找节点
    public boolean contains(int val) {
        ListNode current = head;
        while (current != null) {
            if (current.val == val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 5. 打印链表
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

// 测试链表
public class java0703{
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // 添加元素
        list.append(1);
        list.append(2);
        list.append(3);
        list.prepend(0);

        // 打印链表: 0 -> 1 -> 2 -> 3 -> null
        list.printList();

        // 删除元素
        list.delete(2);

        // 打印链表: 0 -> 1 -> 3 -> null
        list.printList();

        // 查找元素
        System.out.println("Contains 3: " + list.contains(3)); // true
        System.out.println("Contains 2: " + list.contains(2)); // false
    }
}